package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-03
 */

/**
 * 泰波那契序列Tn定义如下：
 *
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 *
 * 给你整数n，请返回第 n 个泰波那契数Tn 的值。
 */
public class leetcode1137 {
    public int tribonacci(int n) {
        if (n==0) return 0;
        if (n==1||n==2) return 1;
        int[] dp = new int[n+1];
        dp[0]=0;dp[1]=1;dp[2]=1;

        for (int i = 3; i < n+1; i++) {
            dp[i] = dp[i-3]+dp[i-2]+dp[i-1];

        }
        return dp[n];
    }
}
